package leetcode.dp;



//121. 买卖股票的最佳时机
//122. 买卖股票的最佳时机 II
public class MaxProfit {

    public static void main(String[] args) {
        int[] data = {7,1,5,3,6,4};
        System.out.println(maxProfit23(data));
    }

    //动态规划
    public static int maxProfit(int[] prices) {
        int[][] f = new int[prices.length][2];
        if (prices.length<2){
            return 0;
        }
        f[0][0] = 0;
        f[0][1] = -prices[0];
        for (int i = 1;i<prices.length;i++){
            f[i][0] = Math.max(f[i-1][0],f[i-1][1]+prices[i]);
            f[i][1] = Math.max(f[i-1][1],-prices[i]);
        }
        return f[prices.length-1][0];
    }

    //双指针
    public static int maxProfit11(int[] prices) {
        int left = 0, right = 0;
        int idax = 0;
        while ( right != prices.length ){
            idax = Math.max(prices[right] - prices[left], idax);
            if ( prices[right] < prices[left] ) {
                left = right;
            }
            right++;
        }
        return idax;
    }
    //贪心
    public static int maxProfit12(int[] prices) {
            int  min = prices[0];
            int res=0;
            for (int i=1;i<prices.length;i++){
               min =  Math.min(prices[i],min);
               res = Math.max(prices[i]-min,res);
            }
            return res;
    }

    //动态规划
    public static int maxProfit21(int[] prices){
          int[][] f=  new int[prices.length][2];
          if (prices.length<2){
              return 0;
          }
          f[0][0]=0;
          f[0][1] = -prices[0];
        for (int i = 1; i <prices.length ; i++) {
            f[i][0] = Math.max(f[i-1][0],f[i-1][1]+prices[i]);
            f[i][1] = Math.max(f[i-1][1],f[i-1][0]-prices[i]);
        }
          return f[prices.length-1][0];
    }

    //贪心算法
    public static int maxProfit22(int[] prices){
        if (prices.length<2){
            return 0;
        }
        int res = 0;
        for (int i =1;i<prices.length;i++){
            int df = prices[i]-prices[i-1];
            if (df>0){
                res+=df;
            }
        }
        return res;

    }

    public static int maxProfit23(int[] prices){
        int res = 0;
        int tmp = 0;

        for (int i = 1;i<prices.length;i++){
            tmp = prices[i]-prices[i-1];
            if (tmp>0){
              res +=tmp;
            }

        }

        return res;


    }




}
